Disk based operating systems divide a disk into physical sectors which represent the fundamental units for data storage on the disk. A sector is a portion of the circumference of a track on the disk and represents the minimum physical storage unit on the disk. File systems define blocks as some integer multiple number of sectors. Each block represents the minimum logical storage unit for a disk. Therefore, reading and writing data to a disk involves the use of entire blocks. In general purpose disk file systems, block sizes are usually selected to be small (e.g., 512 bytes/block), in order to minimize the waste of disk space in blocks that are only partially filled. Such file systems also attempt to allocate the small blocks in sequential order on the disk, so that large reads and writes to the file can be performed efficiently. However, as files are created, modified, or deleted, the free space on the disk can quickly become scattered so that new files are not allocated disk space which is sequential on the disk. These new files will therefore be physically discontiguous or "fragmented".
Access to blocks in a file that are logically sequential, but discontiguous on the disk is often much slower than access to physically sequential blocks, because a disk seek operation must be performed between accesses to the physically separate blocks on the disk. Usually after many files have been created and deleted on such a file system, some degree of fragmentation is bound to exist. In fact, if application programs are not restricted in the way in which they allocate free disk space to files, there is no general way to prevent the free space from becoming completely fragmented. For real-time applications which depend on a high amount of disk input/output bandwidth, this arbitrary degree of fragmentation may cause a failure due to increased access time to the files.
One common method of reducing file fragmentation is to use an optimization utility program which reorganizes files on a disk so that blocks allocated to each file are sequential and contiguous. However, the use of such a utility requires the user to monitor the degree of disk fragmentation and run the utility when fragmentation poses a problem. Moreover, disk optimizer programs usually take a significant amount of time to run, and prevent access to the disk while optimization is being performed.
Another method to minimize file fragmentation is to increase the block size, so that even if files do become fragmented, fewer seek operations will be required to access a specific amount of contiguous data in the file. However, increasing the block size also increases the memory requirements for buffering, and the disk I/O latency for accessing data. Moreover, simply increasing block size does not ensure that fragmentation will not occur to any degree, and does not ensure that the amount of disk space wasted in blocks that are only partially filled is minimized.
Most general purpose file systems are suitable for use with applications for which a certain amount of fragmentation is allowable and does not adversely affect performance. Certain applications, however, require data transfer operations to disk to be completed within a minimum of time. This time requirement translates to a minimum disk input/output bandwidth and is typically measured in terms of number of bytes written to, or read from, the disk per unit time. For such applications, any amount of file fragmentation may introduce seek operations which increase disk access times beyond the minimum bandwidth requirements. Examples of I/O intensive applications include real-time applications which require extensive disk access.
It is therefore an intended advantage of the present invention to provide a system for allocating block sizes in a disk file system which are large enough to prevent file fragmentation, yet not too large so that disk space is wasted within each block.